package com.linyaonan.leetcode.medium._508;

import java.util.*;

/**
 *
 * 给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。
 *
 *  
 *
 * 示例 1
 * 输入:
 *
 *   5
 *  /  \
 * 2   -3
 * 返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
 *
 * 示例 2
 * 输入:
 *
 *   5
 *  /  \
 * 2   -5
 * 返回 [2]，只有 2 出现两次，-5 只出现 1 次。
 *
 *  
 *
 * 提示： 假设任意子树元素和均可以用 32 位有符号整数表示。
 *
 *
 * @author: Lin
 * @date: 2020/1/19
 */
public class MostFrequentSubtreeSum {
    Map<Integer, Integer> map;
    public int[] findFrequentTreeSum(TreeNode root) {
        map = new HashMap<>();
        dfs(root);
        int max = Integer.MIN_VALUE;
        List<Integer> save = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            Integer key = entry.getKey();
            if (value > max) {
                max = value;
                save.clear();
                save.add(key);
            } else if (value == max) {
                save.add(key);
            }
        }
        int[] result = new int[save.size()];
        for (int i = 0; i < save.size(); i++) {
            result[i] = save.get(i);
        }
        return result;
    }

    private int dfs(TreeNode node) {
        if (node != null) {
            int left = dfs(node.left);
            int right = dfs(node.right);
            int count = node.val + left + right;
            map.put(count, map.getOrDefault(count, 0) +1 );
            return count;
        } else {
            return 0;
        }
    }
}
